Computerized devices and systems control almost every aspect of our life, both as individuals and as a society. Many of the computerized systems gather or use data about computerized systems, products, processes, individuals, and other entities, and have to solve problems. One type of problems, referred to as Constraint Satisfaction Problems (CSPs), comprises a wide range of problems, relevant to fields such as resource allocation, DNA exploration, databases testing, functional verification, and others.
CSPs may be defined by a multiplicity of variables, each of a particular domain, i.e. a set of possible values, and one or more constraints to be met by the combination of values assigned to the variables. Thus, a set of values for the variables, wherein the value of each variable is selected from the respective domain, is a solution if all constraints are met, wherein each constraint may refer to one or more variables.
For example, a two-variable problem may relate to two integer variables, a between 0 and 4, and b between 1 and 5, and a constraint a+b=3. Thus. Out of the 25 possible value combinations, only the combinations of (a=0, b=3), (a=1, b=2) and (a=2, b=1) are valid solutions to the problem.
Exhaustive searching over combinations of all values within the domains of the involved variables, and verifying for each combination whether it complies with the constraints is not only inefficient but also not always feasible, for example in the case of variables having infinite domains.
CSPs may be solved by CSP solvers. CSP solvers often exhibit high complexity, especially when the problems are to be solved within a reasonable time.
CSP solvers typically operate by propagating constraints, i.e., reducing one or more variable domains to a smaller domain, such as but not limited to a singleton domain, which may be based on the constraints and the variable values. The values which are removed from a specific domain during propagation cannot be extended into a satisfying solution or are otherwise invalid. In the example above, given the constraint and the fact that a and b domains contain only non-negative numbers, all numbers which are larger than 3 can be removed from the domains of a and b. Constraint propagation can be followed by selecting values for the variables from the reduced domains. The value combination is then tested to see if it complies with the constraints. If yes, the values may be returned. Otherwise, the solver may backtrack and undo one or more of the selections. The selection and propagation may repeat until a solution is found, or until it is determined that the problem is unsolvable.
Reducing the domains and selecting values may require one or more mathematical or logical operations to be performed on the variables' domains.
Thus, in order to use CSP solvers, each type of variable used in the constraints, such as integer numbers, real numbers, characters, strings, complex types, or others, has to be implemented in a manner that supports the expression of all the values within the domain that can be assigned to the variable, as well as provides for efficient execution of a variety of operations over the domain. Some examples of such operations include the determination of maximum or minimum value, getting the size of the domain, domains' intersection and union (also referred to as join), or others.
Character strings are a specific type of variable that poses significant difficulty for CSP solvers. Some string representations provide flexibility in expressing a wide range of values, but the implementation of some operations over such representations is of high complexity and may not allow a CSP solver to operate efficiently.